Binary Tree Upside Down

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:

Given a binary tree {1,2,3,4,5},

  1.     1
  2.    / \
  3.   2   3
  4.  / \
  5. 4   5

return the root of the binary tree [4,5,2,#,#,3,1].

  1.    4
  2.   / \
  3.  5   2
  4.     / \
  5.    3   1

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public TreeNode upsideDownBinaryTree(TreeNode root) {
  12.     if (root == null || root.left == null && root.right == null)
  13.       return root;
  15.     TreeNode newRoot = upsideDownBinaryTree(root.left);
  17.     root.left.left = root.right;
  18.     root.left.right = root;
  20.     root.left = null;
  21.     root.right = null;
  23.     return newRoot;
  24.   }
  25. }